package com.wrial.kind.doublepointer;
/*
 * @Author  Wrial
 * @Date Created in 13:11 2020/8/7
 * @Description
 *
        Input: 5
        Output: True
        Explanation: 1 * 1 + 2 * 2 = 5
        题目描述：判断一个非负整数是否为两个整数的平方和。
 */

public class SumOfSquareNumbers {


    /**
     * 采用左右指针，右指针最大值一定不会超过sqrt（target）
     * x^2+y^2=target  取极限值，x=0，y=sqrt(target)
     * 比如 target为2  left==right  （极限条件）
     *
     * @param target
     * @return
     */
    public boolean judgeSquareSum(int target) {
        int left = 0;
        int right = (int) Math.sqrt(target);
        while (left <= right) {
            int powSum = left * left + right * right;
            if (powSum == target) {
                return true;
            } else if (powSum > target) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }

}
